"""
https://leetcode.cn/problems/binary-tree-inorder-traversal/description/

94. 二叉树的中序遍历
已解答
简单
相关标签
相关企业
给定一个二叉树的根节点 root ，返回 它的 中序 遍历 。

 

示例 1：


输入：root = [1,null,2,3]
输出：[1,3,2]
示例 2：

输入：root = []
输出：[]
示例 3：

输入：root = [1]
输出：[1]
 

提示：

树中节点数目在范围 [0, 100] 内
-100 <= Node.val <= 100
 

进阶: 递归算法很简单，你可以通过迭代算法完成吗？
"""

# import sys
# import os
# # 获取当前文件所在目录的父目录（适用于导入上级目录的模块）
# current_dir = os.path.dirname(os.path.abspath(__file__))
# parent_dir = os.path.join(current_dir, '..')
# sys.path.append(parent_dir)

# Definition for a binary tree node.
from typing import List, Optional

from tree_node import TreeNode,build_tree_node


# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right


class Solution:
    """
    尽量使用迭代法解决问题
    """
    def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        if root is None:
            return []
        
        result=[]
        def dfs(node):
            if node is None:
                return
            dfs(node.left)
            result.append(node.val)
            dfs(node.right)
            
        dfs(root)
    
        return result

if __name__=='__main__':
    nums=[1,None,2,3]
    tn=build_tree_node(nums)
    
    sol=Solution()
    res=sol.inorderTraversal(tn)
    print(res)

    pass